#[test] // leetcode67. 二进制求和
#[ignore]
fn test029() {
    fn add_binary(a: String, b: String) -> String {
        fn bin2num(a: String) -> u128 {
            let mut result = 0_u128;
            for c in a.chars() {
                let v = if c == '1' { 1_u128 } else { 0 };
                result = 2 * result + v;
            }
            result
        }

        let a = bin2num(a);
        let b = bin2num(b);
        let c = a + b;
        format!("{:b}", c).to_string()
    }

    assert_eq!(add_binary("11".to_string(), "1".to_string()), "100".to_string());
    assert_eq!(add_binary("1010".to_string(), "1011".to_string()), "10101".to_string());
}

#[test] // leetcode66. 加1
#[ignore]
fn test028() {
    fn plus_one(digits: Vec<i32>) -> Vec<i32> {
        let mut tmp = digits;
        tmp.reverse();

        let mut result = Vec::new();
        let mut c = 1;
        for &e in tmp.iter() {
            let sum = e + c;
            result.push(sum % 10);
            c = sum / 10;
        }

        if c != 0 {
            result.push(c);
        }

        result.reverse();
        result
    }

    assert_eq!(plus_one(vec![1, 2, 3]), vec![1, 2, 4]);
    assert_eq!(plus_one(vec![4, 3, 2, 1]), vec![4, 3, 2, 2]);
    assert_eq!(plus_one(vec![9, 9, 9]), vec![1, 0, 0, 0]);
}

#[test]  // leetcode3. 无重复字符的最长子串
#[ignore]
fn test026() {
//    use std::collections::HashSet;
//    fn length_of_longest_substring(s: String) -> i32 {
//        let mut i = 0_usize;
//        let mut j = 0_usize;
//        let mut set = HashSet::new();
//        let mut ans = 0;
//        let array: Vec<char> = s.chars().collect();
//
//        let len = s.chars().count();
//        while i < len && j < len {
//            let char = array.get(j).unwrap();
//            if !set.contains(&char) {
//                set.insert(char);
//                ans = ans.max(set.len());
//                j += 1;
//            } else {
//                let tmp = array.get(i).unwrap();
//                set.remove(&tmp);
//                i += 1;
//            }
//        }
//        ans as i32
//    }

//    fn length_of_longest_substring(s: String) -> i32 {
//        let mut i = 0_usize;
//        let mut j = 0_usize;
//        let array: Vec<char> = s.chars().collect();
//        let mut set = Vec::new();
//        let mut ans = 0;
//
//        let len = array.len();
//        while i < len && j < len {
//            let char = array.get(j).unwrap();
//            if !set.contains(&char) {
//                set.push(char);
//                ans = ans.max(set.len());
//                j += 1;
//            } else {
//                set.remove(0);
//                i += 1;
//            }
//        }
//        ans as i32
//    }

    fn length_of_longest_substring(s: String) -> i32 {
        let mut i = 0_usize;
        let mut ans = 0;
        let array: Vec<char> = s.chars().collect();
        let len = array.len();

        for j in 0..len {
            for k in i..j {
                if array.get(k) == array.get(j) {
                    i = k + 1;
                    break;
                }
            }
            ans = ans.max(j - i + 1);
        }
        ans as i32
    }

    assert_eq!(length_of_longest_substring("abcabcbb".to_string()), 3);
    assert_eq!(length_of_longest_substring("bbbbb".to_string()), 1);
    assert_eq!(length_of_longest_substring("pwwkew".to_string()), 3);
    assert_eq!(length_of_longest_substring("dvdf".to_string()), 3);
}

#[test]  // leetcode38. 报数
#[ignore]
fn test025() {
//    fn count_and_say(n: i32) -> String {
//        let map = [
//            "0",
//            "1",
//            "11",
//            "21",
//            "1211",
//            "111221",
//            "312211",
//            "13112221",
//            "1113213211",
//            "31131211131221",
//            "13211311123113112211",
//            "11131221133112132113212221",
//            "3113112221232112111312211312113211",
//            "1321132132111213122112311311222113111221131221",
//            "11131221131211131231121113112221121321132132211331222113112211",
//            "311311222113111231131112132112311321322112111312211312111322212311322113212221",
//            "132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211",
//            "11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221",
//            "31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211",
//            "1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221",
//            "11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211",
//            "311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311122122111312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221131112311311121321122112132231121113122113322113111221131221",
//            "132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113213221133122112231131122211211131221131112311332211211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211",
//            "111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113222123112221221321132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221",
//            "3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211",
//            "132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113213221132213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221",
//            "1113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123211211131211121311121321123113111231131122112213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211",
//            "31131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113311213211321222122111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311123113322113223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331221122311311222112111312211311123113322112132113213221133122211332111213112221133211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212321121113121112133221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111221221113122112132113121113222112132113213221133122211332111213322112132113213221132231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221",
//            "13211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221232112111312211312113211223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321322113311213212322211322132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212311322123123112111321322123122113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132132211331221122311311222112111312211311123113322112111312211312111322212311322123123112112322211211131221131211132221132213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211",
//            "11131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221232112111312111213322112131112131221121321131211132221121321132132212321121113121112133221121321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122111213122112311311222113111221131221221321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212321121113121112133221132211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112132132112211131221131211132221121321132132212321121113121112133221123113112221131112311332111213211322111213111213211231131211132211121311222113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112211213322112312321123113213221123113112221133112132123222112311311222113111231132231121113112221121321133112132112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212311222122132113213221123113112221133112132123222112311311222113111231133211121321132211121311121321122112133221123113112221131112311332211322111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221",
//            "3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211",
//        ];
//        map[n as usize].to_string()
//    }

    fn count_and_say(n: i32) -> String {
        fn say_next(say: String) -> String {
            let mut r = String::new();
            let mut current_char = ' ';
            let mut count = 0;
            let mut is_start = true;
            for e in say.chars() {
                if is_start {
                    current_char = e;
                    count = 1;
                    is_start = false;
                    continue;
                }

                if e == current_char {
                    count += 1;
                } else {
                    r.push_str(&format!("{}{}", count, current_char));
                    current_char = e;
                    count = 1;
                }
            }
            r.push_str(&format!("{}{}", count, current_char));
            r
        }

        let mut s = '1'.to_string();
        for _i in 0..n - 1 {
            s = say_next(s);
        }
        s
    }

    assert_eq!(count_and_say(1), "1".to_string());
    assert_eq!(count_and_say(4), "1211".to_string());
    assert_eq!(count_and_say(5), "111221".to_string());
}

#[test]  // leetcode35. 搜索插入位置
#[ignore]
fn test024() {
    fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        let mut left = 0;
        let mut right = nums.len() as i32;

        while left < right {
            let mid = (left + right) / 2;
            if let Some(&value) = nums.get(mid as usize) {
                if value < target {
                    left = mid + 1;
                } else if value > target {
                    right = mid;
                } else {
                    return mid;
                }
            }
        }

        left
    }

    assert_eq!(search_insert(vec![1, 3, 5, 6], 5), 2);
    assert_eq!(search_insert(vec![1, 3, 5, 6], 2), 1);
    assert_eq!(search_insert(vec![1, 3, 5, 6], 7), 4);
    assert_eq!(search_insert(vec![1, 3, 5, 6], 0), 0);
}

#[test]  // leetcode28. 实现strStr()
#[ignore]
fn test023() {
    fn str_str(haystack: String, needle: String) -> i32 {
        match haystack.find(needle.as_str()) {
            Some(index) => index as i32,
            None => -1,
        }
    }

    assert_eq!(str_str("hello".to_string(), "ll".to_string()), 2);
    assert_eq!(str_str("aaaaa".to_string(), "bba".to_string()), -1);
}

#[test]  // leetcode21. 合并两个有序链表
#[ignore]
fn test022() {
    #[derive(PartialEq, Eq, Clone, Debug)]
    struct ListNode {
        val: i32,
        next: Option<Box<ListNode>>,
    }

    impl ListNode {
        #[inline]
        #[allow(dead_code)]
        fn new(val: i32) -> Self {
            ListNode {
                next: None,
                val,
            }
        }
    }

    fn array_to_list(array: Vec<i32>) -> Option<Box<ListNode>> {
        let mut tail = None;
        for i in 0..array.len() {
            let node = ListNode { val: array[i], next: tail };
            tail = Some(Box::new(node));
        }
        tail
    }

    #[allow(dead_code)]
    fn show(list: Option<Box<ListNode>>) {
        let mut node = list;
        while let Some(inner) = node {
            print!("[{}] ", inner.val);
            node = inner.next;
        }
        println!(" ");
    }

    fn reserve(list: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut tail = None;
        let mut node = list;
        while let Some(inner) = node {
            let p = ListNode { val: inner.val, next: tail };
            tail = Some(Box::new(p));
            node = inner.next;
        }
        tail
    }

    fn merge_two_lists(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut tail = None;
        let mut node1 = reserve(l1);
        let mut node2 = reserve(l2);

        loop {
            match (node1.clone(), node2.clone()) {
                (Some(inner1), Some(inner2)) => {
                    if inner1.val <= inner2.val {
                        let p1 = ListNode { val: inner1.val, next: tail };
                        tail = Some(Box::new(p1));
                        node1 = inner1.next;
                    } else {
                        let p2 = ListNode { val: inner2.val, next: tail };
                        tail = Some(Box::new(p2));
                        node2 = inner2.next;
                    }
                }
                (Some(inner1), None) => {
                    let node = ListNode { val: inner1.val, next: tail };
                    tail = Some(Box::new(node));
                    node1 = inner1.next;
                }
                (None, Some(inner2)) => {
                    let node = ListNode { val: inner2.val, next: tail };
                    tail = Some(Box::new(node));
                    node2 = inner2.next;
                }
                (None, None) => { break; }
            }
        }

        tail
    }

    let aa = array_to_list(vec![1, 3, 4]);
    let bb = array_to_list(vec![1, 2, 4]);
    assert_eq!(merge_two_lists(aa, bb), array_to_list(vec![1, 1, 2, 3, 4, 4]));
}

#[test]  // leetcode27. 移除元素
#[ignore]
fn test021() {
    fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        let mut i = 0_usize;
        while i < nums.len() {
            let mut need_inc = true;
            if let Some(&e) = nums.get(i) {
                if e == val {
                    nums.remove(i);
                    need_inc = false;
                }
            }
            if need_inc {
                i += 1;
            }
        }

        nums.len() as i32
    }

    assert_eq!(remove_element(&mut vec![3, 2, 2, 3], 3), 2);
    assert_eq!(remove_element(&mut vec![0, 1, 2, 2, 3, 0, 4, 2], 2), 5);
}

#[test]  // leetcode26. 删除排序数组中的重复项
#[ignore]
fn test020() {
    fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
        nums.dedup();
        nums.len() as i32
    }

    assert_eq!(remove_duplicates(&mut vec![1, 1, 2]), 2);
    assert_eq!(remove_duplicates(&mut vec![0, 0, 1, 1, 1, 2, 2, 3, 3, 4]), 5);
}

#[test]  // leetcode20. 有效的括号
#[ignore]
fn test019() {
//    fn is_valid(s: String) -> bool {
//        let mut ss = s;
//        loop {
//            ss = ss.replace("()", "");
//            ss = ss.replace("[]", "");
//            ss = ss.replace("{}", "");
//
//            if ss.find("()") == None &&
//                ss.find("[]") == None &&
//                ss.find("{}") == None {
//                break;
//            }
//        }
//
//        ss == ""
//    }

    fn is_valid(s: String) -> bool {
        let mut ss = Vec::new();
        for e in s.chars() {
            match e {
                '(' => ss.push('('),
                '[' => ss.push('['),
                '{' => ss.push('{'),
                ')' => if ss.pop() != Some('(') { return false; },
                ']' => if ss.pop() != Some('[') { return false; },
                '}' => if ss.pop() != Some('{') { return false; },
                _ => return false,
            }
        }

        ss.is_empty()
    }

    assert_eq!(is_valid("()".to_string()), true);
    assert_eq!(is_valid("()[]{}".to_string()), true);
    assert_eq!(is_valid("(]".to_string()), false);
    assert_eq!(is_valid("([)]".to_string()), false);
    assert_eq!(is_valid("{[]}".to_string()), true);
}

#[test]  // leetcode14-最长公共前缀
#[ignore]
fn test018() {
    fn longest_common_prefix(strs: Vec<String>) -> String {
        let mut result = String::new();
        let a = strs.iter().min_by(|x, y| x.cmp(y));
        let b = strs.iter().max_by(|x, y| x.cmp(y));
        if a == None || b == None {
            return result;
        }

        let a = a.unwrap();
        let b = b.unwrap();
        let mut i = 0;
        loop {
            match (a.chars().nth(i), b.chars().nth(i)) {
                (Some(m), Some(n)) => {
                    if m != n { break; }
                    result.push(m);
                }
                _ => break,
            }
            i += 1;
        }

        result
    }

    assert_eq!(longest_common_prefix(vec!["flower".to_string(), "flow".to_string(), "flight".to_string()]), "fl".to_string());
    assert_eq!(longest_common_prefix(vec!["dog".to_string(), "racecar".to_string(), "car".to_string()]), "".to_string());
}

#[test]  // leetcode13-罗马数字转整数
#[ignore]
fn test017() {
    use std::collections::HashMap;
    fn roman_to_int(s: String) -> i32 {
        let map: HashMap<char, i32> = [
            ('I', 1),
            ('V', 5),
            ('X', 10),
            ('L', 50),
            ('C', 100),
            ('D', 500),
            ('M', 1000),
        ].iter().cloned().collect();
        let mut result = 0;
        let chars: Vec<char> = s.chars().collect();

        for i in 0..chars.len() {
            let current = chars.get(i).unwrap();
            let next = chars.get(i + 1);
            let &current_value = map.get(&current).unwrap();
            let &next_value = match next {
                Some(n) => map.get(&n).unwrap(),
                None => &0,
            };

            if current_value < next_value {
                result -= current_value;
            } else {
                result += current_value;
            }
        }
        result
    }

//    fn roman_to_int(s: String) -> i32 {
//        let map: HashMap<char, i32> = [
//            ('I', 1),
//            ('V', 5),
//            ('X', 10),
//            ('L', 50),
//            ('C', 100),
//            ('D', 500),
//            ('M', 1000),
//
//            ('N', 4),
//            ('O', 9),
//            ('P', 40),
//            ('Q', 90),
//            ('R', 400),
//            ('S', 900),
//        ].iter().cloned().collect();
//        let replace_pair = [
//            ("IV", "N"),
//            ("IX", "O"),
//            ("XL", "P"),
//            ("XC", "Q"),
//            ("CD", "R"),
//            ("CM", "S"),
//        ];
//
//        let mut ss = s;
//        for e in &replace_pair {
//            ss = ss.replace(e.0, e.1);
//        }
//
//        let mut result = 0;
//        for e in ss.chars() {
//            if let Some(&i) = map.get(&e) {
//                result += i;
//            }
//        }
//        result
//    }

    assert_eq!(roman_to_int("III".to_string()), 3);
    assert_eq!(roman_to_int("IV".to_string()), 4);
    assert_eq!(roman_to_int("IX".to_string()), 9);
    assert_eq!(roman_to_int("LVIII".to_string()), 58);
    assert_eq!(roman_to_int("MCMXCIV".to_string()), 1994);
}

#[test]  // leetcode9-回文数
#[ignore]
fn test016() {
    fn is_palindrome(x: i32) -> bool {
        if x < 0 {
            return false;
        }

        if x == 0 {
            return true;
        }

        let mut n: i32 = x;
        let mut result: i32 = 0;
        while n > 0 {
            result = 10 * result + n % 10;
            n /= 10;
        }

        x == result
    }


//    fn is_palindrome(x: i32) -> bool {
//        if x < 0 {
//            return false;
//        }
//
//        let s = x.to_string();
//        let r: String = s.chars().rev().collect();
//        s == r
//    }

    assert_eq!(is_palindrome(121), true);
    assert_eq!(is_palindrome(-121), false);
    assert_eq!(is_palindrome(10), false);
}

#[test]  // leetcode1-整数反转
#[ignore]
fn test015() {
    fn reverse(x: i32) -> i32 {
        let mut n: i32 = x.abs();
        let mut result: i32 = 0;

        while n > 0 {
            if result.checked_mul(10) == None || (10 * result).checked_add(n % 10) == None {
                return 0;
            }
            result = 10 * result + n % 10;
            n /= 10;
        }

        result * x.signum()
    }

    assert_eq!(reverse(123), 321);
    assert_eq!(reverse(-123), -321);
    assert_eq!(reverse(120), 21);
    assert_eq!(reverse(1534236469), 0);
}

#[test]  // 链表1
#[ignore]
fn test014() {
    use std::mem;

    struct List {
        head: Link,
    }

    enum Link {
        Empty,
        More(Box<Node>),
    }

    struct Node {
        elem: i32,
        next: Link,
    }

    impl List {
        fn new() -> Self {
            List { head: Link::Empty }
        }

        fn push(&mut self, val: i32) {
            let new_node = Box::new(Node { elem: val, next: mem::replace(&mut self.head, Link::Empty) });
            self.head = Link::More(new_node);
        }

        fn pop(&mut self) -> Option<i32> {
            match mem::replace(&mut self.head, Link::Empty) {
                Link::Empty => None,
                Link::More(node) => {
                    self.head = node.next;
                    Some(node.elem)
                }
            }
        }
    }

    impl Drop for List {
        fn drop(&mut self) {
            let mut cur_link = mem::replace(&mut self.head, Link::Empty);
            while let Link::More(mut boxed_node) = cur_link {
                cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
            }
        }
    }

    let mut list = List::new();
    assert_eq!(list.pop(), None);

    list.push(1);
    list.push(2);
    list.push(3);

    assert_eq!(list.pop(), Some(3));
    assert_eq!(list.pop(), Some(2));
    assert_eq!(list.pop(), Some(1));
    assert_eq!(list.pop(), None);
    assert_eq!(list.pop(), None);
}

#[test]  // leetcode2-两数相加
#[ignore]
fn test013() {
    #[derive(PartialEq, Eq, Clone, Debug)]
    struct ListNode {
        val: i32,
        next: Option<Box<ListNode>>,
    }

    impl ListNode {
        #[inline]
        #[allow(dead_code)]
        fn new(val: i32) -> Self {
            ListNode {
                next: None,
                val,
            }
        }
    }

    fn show(list: Option<Box<ListNode>>) {
        let mut node = list;
        while let Some(inner) = node {
            print!("[{}] ", inner.val);
            node = inner.next;
        }
        println!(" ");
    }

    fn array_to_list(array: Vec<i32>) -> Option<Box<ListNode>> {
        let mut tail = None;
        for i in 0..array.len() {
            let node = ListNode { val: array[i], next: tail };
            tail = Some(Box::new(node));
        }
        tail
    }

    fn list_to_array(list: Option<Box<ListNode>>) -> Vec<i32> {
        let mut array = Vec::new();
        let mut node = list;
        while let Some(inner) = node {
            array.push(inner.val);
            node = inner.next;
        }
        array
    }

    fn add_two_array(a: Vec<i32>, b: Vec<i32>) -> Vec<i32> {
        let mut array = Vec::new();
        let max_len = a.len().max(b.len());
        let mut c = 0;

        for i in 0..max_len {
            let (d1, d2) = match (a.get(i), b.get(i)) {
                (Some(n1), Some(n2)) => (*n1, *n2),
                (Some(n1), None) => (*n1, 0),
                (None, Some(n2)) => (0, *n2),
                (None, None) => break,
            };

            let num = d1 + d2 + c;
            let n = num % 10;
            c = num / 10;
            array.push(n);
        }

        if c != 0 {
            array.push(c);
        }

        array
    }

    fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let list1 = list_to_array(l1);
        let list2 = list_to_array(l2);
        let mut sum_array = add_two_array(list1, list2);
        sum_array.reverse();
        array_to_list(sum_array)
    }

    let aa = array_to_list(vec![2, 4, 3]);
    let bb = array_to_list(vec![5, 6, 4]);
    show(add_two_numbers(aa, bb));
}

#[test]  // leetcode1-两数之和
#[ignore]
fn test012() {
    let a = vec![3, 2, 4];
    let b = 6;
    let c = two_sum(a, b);
    println!("{:?}", c);

    use std::collections::HashMap;
    fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut map = HashMap::with_capacity(nums.len());
        for i in 0..nums.len() {
            map.insert(nums[i], i);
        }
//        println!("{:?}", map);

        for i in 0..nums.len() {
            let left = target - nums[i];
            if let Some(&j) = map.get(&left) {
                if i != j {
                    return vec![i as i32, j as i32];
                }
            }
        }

        vec![]
    }

    #[allow(dead_code)]
    fn two_sum_normal(nums: Vec<i32>, target: i32) -> Vec<i32> {
        for i in 0..nums.len() {
            for j in (i + 1)..nums.len() {
                if nums[i] + nums[j] == target {
                    return vec![i as i32, j as i32];
                }
            }
        }

        vec![]
    }
}

fn main() {
    println!("hello, world!");
}

